package com.zx._12_算法.剑指offer._2022;

public class 接水滴 {

    public static void main(String[] args) {
        int[] arr = {4, 2, 3};// 1
//		int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};//6

        int trap = new 接水滴().trap(arr);
        System.out.println(trap);
    }

    public int trap(int[] height) {
        int beginNoZore = 0;
        // 确认开头
        for (int i = 0; i < height.length; i++) {
            if (height[i] != 0) {
                beginNoZore = i;
                break;
            }
        }

        int begin = beginNoZore;
        int end = beginNoZore + 1;
        int res = 0;
        while (begin + 1 < height.length) {
            int beginNum = height[begin];
            end = maxFirst(height, begin + 1, height.length - 1, beginNum);
            if (end == -1) {
                end = maxSecond(height, begin + 1, height.length - 1, beginNum);
            }

            if (end == -1) {
                break;
            }

            int sum = sum(height, begin, end);
            if (sum > 0) {
                res += sum;
            }

            begin = end;
        }
        return res;
    }

    // 找到第一个比num大的
    public int maxFirst(int[] arr, int begin, int end, int num) {
        // 找到大于等于的索引位置
        for (int i = begin; i <= end; i++) {
            int max = arr[i];
            if (max >= num) {
                return i;
            }
        }
        return -1;
    }

    // 找到第一个比num小的最高的，已经确认没有大于num的数字了
    public int maxSecond(int[] arr, int begin, int end, int num) {
        // 找到大于等于的索引位置
        int max = arr[begin];
        int maxIdx = begin;
        for (int i = begin; i <= end; i++) {
            if (arr[i] > max) {
                maxIdx = i;
                max = arr[i];
            }
        }
        return maxIdx;
    }

    public int sum(int[] arr, int begin, int end) {
        int sum = 0;
        int min = arr[begin] > arr[end] ? arr[end] : arr[begin];
        for (int i = begin; i <= end; i++) {
            int t = min - arr[i];
            if (t > 0) {
                sum += t;
            }
        }
        return sum;
    }


}
